package de.rs.espresso.algorithms;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

import de.rs.espresso.algorithms.minimumcover.MinimumCover;
import de.rs.espresso.algorithms.minimumcover.model.Solution;
import de.rs.espresso.algorithms.model.FreeSet;
import de.rs.espresso.covers.DefaultCover;
import de.rs.espresso.cubes.CubeFactory;
import de.rs.espresso.cubes.FreezedCube;
import de.rs.espresso.interfaces.IAlgorithm;
import de.rs.espresso.interfaces.ICover;
import de.rs.espresso.interfaces.ICube;
import de.rs.espresso.interfaces.IGlobalInformation;
import de.rs.espresso.tools.Statistics;

public class Expand implements IAlgorithm {

	private ICover onSet;
	private ICover offSet;
	private IGlobalInformation info;
	
	public Expand(IGlobalInformation info) {
		this.info = info;
	}

	@Override
	public ICover compute(ICover onSet, ICover offSet, ICover dcSet) {
		
		long measurementId = Statistics.startMeasurement("EXPAND");

		this.onSet = onSet;
		this.offSet = offSet;

		onSet.sortByCubeWeight();

		
		while(true) {
			ICube toExpand = null;
			for(ICube cube : onSet) {
				if(!cube.isAlreadyExpanded()) {
					toExpand = cube;
					break;
				}
			}
			
			if(toExpand == null)
				break;
			
			expandCube(toExpand);
			
		}
		
		for(ICube cube : onSet) {
			cube.setAlreadyExpanded(false);
		}

		
		Statistics.stopMeasurement(measurementId); 
		
		return onSet;
	}

	/*
	 * 
	 * @param alpha
	 */
	private void expandCube(ICube alpha) {
		FreeSet fSet = alpha.getFreeSet();
		fSet.removeEssentials(offSet);
		
		
		// STEP 2: Detection of feasibly covered Cubes
		
		List<ICube> feasiblyCoveredCubes = getFeasiblyCoveredCubes(alpha);
		
		while(!feasiblyCoveredCubes.isEmpty()) {
			
			int maxCoverCount = Integer.MIN_VALUE;
			ICube beta = null;
			int coverCount;
			for (ICube cube : feasiblyCoveredCubes) {
				coverCount = 0;
				for (ICube otherCube : feasiblyCoveredCubes)
					if (cube!=otherCube&&cube.covers(otherCube))
						coverCount++;
				if (coverCount >= maxCoverCount) {
					beta = cube;
					maxCoverCount = coverCount;

				}
			}
			
			ICube superCube = alpha.getSupercube(beta);
			
			onSet.remove(alpha);
			onSet.remove(beta);
			onSet.add(superCube);
			
			fSet.changeCube(superCube);
			fSet.removeSetPartsOf(beta);
			fSet.removeEssentials(offSet);
			
			alpha = superCube;
			
			feasiblyCoveredCubes = getFeasiblyCoveredCubes(alpha);
			
		}
		
		// STEP 3: Expansion Guided by the Overexpanded Cube

		ICube overexpandedCube = fSet.getOverexpandedCube();
		ICover coveredCubes = getCoveredCubes(overexpandedCube);
		
		while(!coveredCubes.isEmpty()&&!fSet.isEmpty()) {
			
				int value = fSet.popMostOccuringPart(coveredCubes);
		
				alpha.raisePart(value);
		
				fSet.removeEssentials(offSet);
				
				overexpandedCube = fSet.getOverexpandedCube();
				coveredCubes = getCoveredCubes(overexpandedCube);
		}
		

		//STEP 4: Make it prime!
		
		if(!fSet.isEmpty()) {
			List<BitSet> rows = getRows(alpha);
			List<Column> columns = getColumns();
					
			ICube result = getResult(new MinimumCover<Column>(columns, rows).compute().toList(), alpha);
			
			onSet.remove(alpha);
			onSet.add(result);
			result.setAlreadyExpanded(true);
		}
		else {
			alpha.setAlreadyExpanded(true);
		}
		

		
		

	}

	private ICube getResult(List<Column> solutions, ICube alpha) {
		ICube result = CubeFactory.getDontCareCube(info);
		
		for(Column solution : solutions) {
			if(solution.getType()==ColumnType.INPUT) {
				result.setLiteral(solution.getPosition(), alpha.getLiteral(solution.getPosition()));
			}
			else {
				result.setOutput(solution.getPosition(), alpha.getOutput(solution.getPosition()));
			}
		}
		
		return result;
	}

	private ICover getCoveredCubes(ICube overexpandedCube) {
		DefaultCover coveredCubeList = new DefaultCover(info);

		for (ICube beta : onSet) {
		
			if(!overexpandedCube.equals(beta)&&overexpandedCube.covers(beta))
				coveredCubeList.add(beta);
			
		}
		
		return coveredCubeList;
	}

	/*
	 * Returns all Cubes except alpha, whose supercube with alpha do not intersect the offset.
	 * 
	 */
	private List<ICube> getFeasiblyCoveredCubes(ICube alpha) {

		ArrayList<ICube> feasiblyCoveredCubeList = new ArrayList<ICube>();

		for (ICube beta : onSet) {
			if (!alpha.equals(beta) || !alpha.covers(beta)) {

				ICube superCube = alpha.getSupercube(beta);

				if (!offSet.intersect(superCube)) {

					feasiblyCoveredCubeList.add(beta);

				}

			}
		}
		return feasiblyCoveredCubeList;

	}
	
	/*
	 * 
	 */
	private List<BitSet> getRows(ICube alpha) {
		List<BitSet> rows = new ArrayList<BitSet>();

		
		for(ICube offSetCube : offSet) {
			BitSet bitSet = new BitSet(info.getNumberOfInputs()+info.getNumberOfOutputs());
			ICube c = alpha.and(offSetCube);
			for(int i = 0; i < info.getNumberOfInputs(); i++) {
				if(c.getLiteral(i)==ICube.VOID) {
					bitSet.set(i);
				}
			}
			for(int i = 0; i < info.getNumberOfOutputs(); i++) {
				if(alpha.getOutput(i)==ICube.OUTPUT_NOT_PRESENT&&offSetCube.getOutput(i)==ICube.OUTPUT_PRESENT) {
					bitSet.set(i+info.getNumberOfInputs());
				}
			}
			rows.add(bitSet);			
		}
		
		return rows;
		
	}
	
	private List<Column> getColumns() {
		List<Column> columns = new ArrayList<Column>();
		
		for(int i = 0; i < info.getNumberOfInputs(); i++) {
			columns.add(new Column(ColumnType.INPUT, i));
		}
		for(int i = 0; i < info.getNumberOfOutputs(); i++) {
			columns.add(new Column(ColumnType.OUTPUT, i));
		}
		
		return columns;
		
	}

	public enum ColumnType {
		OUTPUT,INPUT
	}
	
	public class Column {
		private ColumnType type;
		private int position;
		
		
		public Column(ColumnType type, int position) {
			this.position = position;
			this.type = type;
		}


		public int getPosition() {
			return position;
		}


		public ColumnType getType() {
			return type;
		}
	}
}
